#include <map>
#include <set>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

template<class vertexType, class edgeType>
class Graph
{
public:
    typedef typename map<vertexType, set<pair<vertexType, edgeType> > >::iterator VertexMapIterator;
    class EdgeIterator;
    
    class VertexIterator //Итератор по вершинам
    {
    public:
        VertexIterator(const VertexIterator&);
        VertexIterator(const Graph<vertexType, edgeType>*, const typename map<vertexType, set<pair<vertexType, edgeType> > >::iterator&);
        VertexIterator(Graph<vertexType, edgeType>*, vertexType);
        
        EdgeIterator GetOutGoingEdgesBegin(); //Итератор по ребрам выходищим из данной вершины (начало)
        EdgeIterator GetOutGoingEdgesEnd(); //Итератор по ребрам выходищим из данной вершины (конец)
        
        pair<vertexType, set<pair<vertexType, edgeType> > >& operator *(); //Перегруженный оператор *
        const pair<vertexType, set<pair<vertexType, edgeType> > >& operator *() const;
        
        VertexIterator& operator =(const VertexIterator&);
        VertexIterator& operator ++();
        
        bool operator ==(const VertexIterator&) const;
        bool operator !=(const VertexIterator& other) const {return !operator ==(other);};
        
    private:
        const Graph<vertexType, edgeType>* graphPointer;
        VertexMapIterator vertexListIterator;
    };
    
    typedef typename set<pair<vertexType, edgeType> >::iterator EdgeMatrixIterator; //итератор по set
    class EdgeIterator
    {
    public:
        
        EdgeIterator(const EdgeIterator&);
        EdgeIterator(const Graph<vertexType, edgeType>*, const EdgeMatrixIterator&); //конструктор по графу и итератору по set
        
        pair<vertexType, edgeType>& operator*(); //Оператор * возвращает пару чисел: куда идет ребро и его вес
        const pair<vertexType, edgeType>& operator*() const;
        
        EdgeIterator& operator =(const EdgeIterator& other);
        EdgeIterator& operator ++();
        
        bool operator ==(const EdgeIterator& other) const;
        bool operator !=(const EdgeIterator& other) const { return !operator==(other); };
        
    private:
        
        const Graph<vertexType, edgeType>* graphPointer;
        EdgeMatrixIterator edgeMatrixIterator;
    };
    
    
    Graph(map<vertexType, set<pair<vertexType, edgeType> > >); //конструктор по map из вершин и ребер
    
    VertexIterator begin() {return VertexIterator(this, graph.begin());} //Итератор на начало списка вершин
    VertexIterator end() {return VertexIterator(this, graph.end());} //Итератор на конец списка вершин
    EdgeIterator getOutGoingEdgesBegin(vertexType root){return (VertexIterator(this, root)).GetOutGoingEdgesBegin();} //Итератор по ребрам выходящим из вершины
    EdgeIterator getOutGoingEdgesEnd(vertexType root){return (VertexIterator(this, root)).GetOutGoingEdgesEnd();}
    
    bool addEdge(vertexType, vertexType, edgeType); //добавить ребро
    int getNumOfVertex(); //получить число вершин
    int getNumOfEdges(); //получить число всех ребер в графе
private:
    map<vertexType, set<pair<vertexType, edgeType> > > graph; //граф
    int edgeNum;
    int vertexNum;
};

///////////////////////////////////////////////////////////////////////
////////////////////////////VERTEX_ITERATOR////////////////////////////
///////////////////////////////////////////////////////////////////////

template <class vertexType, class edgeType>
Graph<vertexType, edgeType>::VertexIterator::VertexIterator(const VertexIterator& other)
{
    this->vertexListIterator = other.vertexListIterator;
    this->graphPointer = other.graphPointer;
}

template <class vertexType, class edgeType>
Graph<vertexType, edgeType>::VertexIterator::VertexIterator(const Graph<vertexType, edgeType>* graph,
                                                            const typename map<vertexType, set<pair<vertexType, edgeType>>>::iterator& iter)
{
    graphPointer = graph;
    vertexListIterator = iter;
}

template <class vertexType, class edgeType>
Graph<vertexType, edgeType>::VertexIterator::VertexIterator(Graph<vertexType, edgeType>* gr,
                                                            vertexType vertex)
{
    graphPointer = gr;
    vertexListIterator = gr->graph.find(vertex);
}

template <class vertexType, class edgeType>
typename Graph<vertexType, edgeType>::EdgeIterator Graph<vertexType, edgeType>::VertexIterator::GetOutGoingEdgesBegin()
{
    
    typename map<vertexType, set<pair<vertexType, edgeType> > >::iterator map_iterator;
    map_iterator = (typename map<vertexType, set<pair<vertexType, edgeType> >>::iterator)this->vertexListIterator;
    return EdgeIterator(this->graphPointer, map_iterator->second.begin());
}

template <class vertexType, class edgeType>
typename Graph<vertexType, edgeType>::EdgeIterator Graph<vertexType, edgeType>::VertexIterator::GetOutGoingEdgesEnd()
{
    typename map<vertexType, set<pair<vertexType, edgeType> > >::iterator map_iterator;
    map_iterator = (typename map<vertexType, set<pair<vertexType, edgeType> >>::iterator)this->vertexListIterator;
    return EdgeIterator(this->graphPointer, map_iterator->second.end());
}

template <class vertexType, class edgeType>
pair<vertexType, set<pair<vertexType, edgeType> > >& Graph<vertexType, edgeType>::VertexIterator::operator*()
{
    return reinterpret_cast<pair<vertexType, set<pair<vertexType, edgeType>>>& >(*vertexListIterator);
}

template <class vertexType, class edgeType>
const pair<vertexType, set<pair<vertexType, edgeType> > >& Graph<vertexType, edgeType>::VertexIterator::
operator*() const
{
    return *vertexListIterator;
}

template <class vertexType, class edgeType>
class Graph<vertexType, edgeType>::VertexIterator&
Graph<vertexType, edgeType>::VertexIterator::
operator =(const Graph<vertexType, edgeType>::VertexIterator& other)
{
    if (this->vertexListIterator != other.vertexListIterator)
    {
        this->vertexListIterator = other.vertexListIterator;
        this->graphPointer = other.graphPointer;
    }
    return *this;
}

template <class vertexType, class edgeType>
class Graph<vertexType, edgeType>::VertexIterator&
Graph<vertexType, edgeType>::VertexIterator::
operator ++()
{
    ++vertexListIterator;
    return *this;
}

template <class vertexType, class edgeType>
bool Graph<vertexType, edgeType>::VertexIterator::
operator == (const Graph<vertexType, edgeType>::VertexIterator& other) const
{
    return (vertexListIterator == other.vertexListIterator);
}

/////////////////////////////////////////////////////////////////////
////////////////////////////EDGE_ITERATOR////////////////////////////
/////////////////////////////////////////////////////////////////////

template <typename vertexType, typename edgeType>
Graph<vertexType, edgeType>::EdgeIterator::EdgeIterator
(const EdgeIterator& other)
{
    this->graphPointer = other.graphPointer;
    this->edgeMatrixIterator = other.edgeMatrixIterator;
}

template <typename vertexType, typename edgeType>
Graph<vertexType, edgeType>::EdgeIterator::EdgeIterator
(const Graph<vertexType, edgeType>* graph, const EdgeMatrixIterator& it)
{
    this->graphPointer = graph;
    this->edgeMatrixIterator = it;
}

template <typename vertexType, typename edgeType>
pair<vertexType, edgeType>& Graph<vertexType, edgeType>::EdgeIterator::operator*()
{
    return const_cast<pair<vertexType, edgeType>&>(*edgeMatrixIterator);
}

template <typename vertexType, typename edgeType>
const pair<vertexType, edgeType>& Graph<vertexType, edgeType>::EdgeIterator::operator*() const
{
    return *(*edgeMatrixIterator);
}

template <typename vertexType, typename edgeType>
typename Graph<vertexType, edgeType>::EdgeIterator& Graph<vertexType, edgeType>::
EdgeIterator::operator =(const EdgeIterator& other)
{
    if (this->edgeMatrixIterator != other.edgeMatrixIterator)
    {
        this->graphPointer = other.graphPointer;
        this->edgeMatrixIterator = other.edgeMatrixIterator;
    }
    return *this;
}

template <typename vertexType, typename edgeType>
typename Graph<vertexType, edgeType>::EdgeIterator& Graph<vertexType, edgeType>::
EdgeIterator::operator ++()
{
    ++(this->edgeMatrixIterator);
    return *this;
}

template <typename vertexType, typename edgeType>
bool Graph<vertexType, edgeType>::EdgeIterator::
operator==(const Graph<vertexType, edgeType>::EdgeIterator& other) const
{
    return (this->edgeMatrixIterator == other.edgeMatrixIterator);
    
}

/////////////////////////////////////////////////////////////
////////////////////////////GRAPH////////////////////////////
/////////////////////////////////////////////////////////////

template<class vertexType ,class edgeType>
Graph<vertexType, edgeType>::
Graph(map<vertexType, set<pair<vertexType, edgeType> > > _graph)
{
    graph = _graph;
    edgeNum = 0;
    vertexNum = (int)graph.size();
    for(auto it = graph.begin(); it != graph.end(); it++)
        for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++)
            edgeNum++;
}

template<class vertexType, class edgeType>
Graph<vertexType, edgeType> readGraphFromIOstream() //чтение данных с клавиатуры
{
    int is_oriented, edgeNum = 0;
    cin >> edgeNum >> is_oriented; //считываем число ребер и ориентированный или нет граф
    std::map<vertexType, set<pair<vertexType, int> > > graph; //при чтении ребра записываем сначала сюда
    edgeType edgeWeight;
    vertexType e1, e2;
    std::set<std::pair<vertexType, int> > clear_set;
    std::pair<typename std::map<vertexType, std::set<std::pair<vertexType, int> > >::iterator, bool> result;
    
    for (int i = 0; i < edgeNum; i++) //считываем ребра
    {
        std::cin >> e1 >> e2 >> edgeWeight; //считываем информацию о ребре: откуда, куда и вес
        
        result = graph.insert(make_pair(e1, clear_set));
        if (graph.find(e2) == graph.end())
            graph.insert(make_pair(e2, clear_set));
        result.first->second.insert(std::make_pair(e2, edgeWeight));
    }
    Graph<vertexType, edgeType> g1(graph);
    return g1;
}

template<class vertexType, class edgeType>
int Graph<vertexType, edgeType>::getNumOfVertex()
{
    return (int)graph.size();
}

template<class vertexType, class edgeType>
int Graph<vertexType, edgeType>::getNumOfEdges()
{
    int edgenum = 0;
    for (auto it = graph.begin(); it != graph.end(); it++)
        for (auto it2 = it->second.begin(); it2 != it->second.end(); it2++)
            edgenum++;
    return edgenum;
}

template<class vertexType, class edgeType>
bool Graph<vertexType, edgeType>::addEdge(vertexType v1, vertexType v2, edgeType edgeWeight)
{
    set<pair<vertexType, edgeType> > clearSet;
    if (graph.find(v1) == graph.end())
        graph.insert(make_pair(v1, clearSet));
    if (graph.find(v2) == graph.end())
        graph.insert(make_pair(v2, clearSet));
    graph.find(v1)->second.insert(make_pair(v2, edgeWeight));
}
//////////////////////////////////////////////////////////////////
////////////////////////////ALGORITHMS////////////////////////////
//////////////////////////////////////////////////////////////////

template<class vertexType, class edgeType>
struct Tarjan_info //вспомогательная структура для алгоритма Тарьяна(для сохранения данных при рекурсии)
{
    map<vertexType, int> tin; //время входа в вершину
    map<vertexType, int> f; //значение функции для вершины
    int times = 0; //счетчик времени
    int vertexNum;  //кол-во вершин в графе
    int SCCnum = 0; //на входе из алгоритма тут будет лежать кол-во КСС
};

template<class vertexType, class edgeType>
void Tarjan_algo(Graph<vertexType, edgeType>& gr, vertexType root, std::map<vertexType, int>& color, Tarjan_info<vertexType, edgeType>& info) //Поиск КСС в графе
//gr, из вершины root, в массиве color на выходе в color[i] будет лежать номер КСС в которую входит
//i-ая вершина, info - вспомогательная информация для рекурсии
{
    static stack<vertexType> DFSstack;
    
    if (info.tin.find(root)->second == 0)
    {
        DFSstack.push(root);
        info.f.find(root)->second = info.tin.find(root)->second = ++info.times;
        for(auto it = gr.getOutGoingEdgesBegin(root); it != gr.getOutGoingEdgesEnd(root); ++it)
        {
            if (color.find((*it).first)->second == 0)
            {
                if (info.tin.find((*it).first)->second == 0)
                    Tarjan_algo(gr, (*it).first, color, info);
                info.f.find(root)->second = std::min(info.f.find(root)->second, info.f.find((*it).first)->second);
            }
        }
        if (info.f.find(root)->second == info.tin.find(root)->second)
        {
            vertexType u;
            info.SCCnum++;
            do {
                u = DFSstack.top();
                color.find(u)->second = info.SCCnum;
                DFSstack.pop();
            } while (u != root);
        }
    }
}



template<class vertexType, class edgeType>
void SCCsearch(Graph<vertexType, edgeType>& gr, vector<vector<vertexType> >& result) //подготовка данных и обработка выходных данных для алгоритма Тарьяна, в result[i] будут лежать все вершины по порядку, входящие в i-ую КСС
{
    Tarjan_info<vertexType, edgeType> tmp;
    for (auto it = gr.begin(); it != gr.end(); ++it)
    {
        tmp.tin.insert(make_pair((*it).first, 0));
        tmp.f.insert(make_pair((*it).first, 0));
    }
    tmp.SCCnum = 0;
    tmp.times = 0;
    tmp.vertexNum = gr.getNumOfVertex();
    std::map<vertexType, int> color;
    for (auto it = gr.begin(); it != gr.end(); ++it)
        color.insert(make_pair((*it).first, 0));
    
    Tarjan_algo<vertexType, edgeType>(gr, (*(gr.begin())).first, color, tmp); //запускаем Тарьяна из 0-ой вершины
    
    for (auto it = color.begin(); it != color.end(); it++) //если остались вершины, не входяшие ни в одну КСС то запускаем Тарьяна из них
        if (it->second == 0)
            Tarjan_algo<vertexType, edgeType>(gr, it->first, color, tmp);
    
    std::vector<vertexType> sampleVect; //далее идет заполнение result и очиска памяти
    for(int i = 0; i < tmp.SCCnum; i++)
        result.push_back(sampleVect);
    for (auto it = color.begin(); it != color.end(); it++)
        result[it->second - 1].push_back(it->first);
}

template<class vertexType, class edgeType>
bool fordBellman(Graph<vertexType, edgeType>& gr, vertexType root, map<vertexType, edgeType>& distance) //Алгоритм Форда Беллмана, на вход получает граф gr, вершину root из которой будем искать, в distance[i] будет лежать расстояние от вершины root до i-ой вершины
{
    for (auto it = gr.begin(); it != gr.end(); ++it)
        distance.insert(make_pair((*it).first, numeric_limits<edgeType>::max() - 10)); //заполняем заведомо большими рассояниями
    distance[root] = (edgeType) 0;
    
    for (int iter = 0; iter < gr.getNumOfVertex() - 1; ++iter) {//|V| раз релаксируем ребра
        for (auto v = gr.begin(); v != gr.end(); ++v) { // перебираем каждую вершину из которой есть хотя бы одно ребро
            for (auto e = gr.getOutGoingEdgesBegin((*v).first); e != gr.getOutGoingEdgesEnd((*v).first); ++e) { //перебираем все ребра из вершины v и при необходимости обновляем расстояние
                if (distance.find((*e).first)->second > distance.find((*v).first)->second + (*e).second) {
                    distance.find((*e).first)->second = distance.find((*v).first)->second + (*e).second;
                }
            }
        }
    }
    
    for (auto v = gr.begin(); v != gr.end(); ++v) { //если на последней итерации мы сделаем релаксацию, то у нас есть цикл отрицательный длины
        for (auto e = gr.getOutGoingEdgesBegin((*v).first); e != gr.getOutGoingEdgesEnd((*v).first); ++e) {
            if (distance.find((*e).first)->second > distance.find((*v).first)->second + (*e).second) {
                return false;
            }
        }
    }
    return true;
}